L2-038 病毒溯源

题目 L2-038 病毒溯源

思路分析

找入度为0的是起点

代码实现

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

using ll = long long;

using ull = unsigned long long;

using PII = pair<int, int>;

using Pll = pair<ll, ll>;

int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };

const int inf = 0x3f3f3f3f;

int maxDeep=-inf;

vector<set<int>> g;

vector<int> path;

vector<int> ans;

vector<bool> visited;

void dfs(int cur,int deep){

	if(deep>maxDeep){

		ans=path;

		maxDeep=deep;

	}

	for(auto ne:g[cur]){

		if(!visited[ne]){

			visited[ne]=true;

			path.push_back(ne);

			dfs(ne,deep+1);

			path.pop_back();

			visited[ne]=false;

		}

	}

}

signed main() {

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n;cin>>n;

	g.resize(n);

	visited.resize(n,false);

	vector<int> indegree(n);

	for(int i=0;i<n;i++){

		int k;cin>>k;

		while(k--){

			int ne;cin>>ne;

			g[i].insert(ne);

			indegree[ne]++;

		}

	}

	int start=-1;

	for(int i = 0; i < n; i++) {

		if(indegree[i] == 0) {

			start = i;

			break;

		}

	}

//	cout<<start;

	dfs(start,1);

	cout<<maxDeep<<endl;

	cout<<start;

	for(auto v:ans){

		cout<<" "<<v;

	}

    return 0;

}

同类题型

视频讲解

⬅️ L2-037 包装机 🏠 00-天梯赛 ➡️ L2-039 清点代码库